package offer;

public class offerII_0090 {
    public int rob(int[] nums) {
        int len=nums.length;
        if(len==1)return nums[0];
        if(len==2) return Math.max(nums[0],nums[1]);
        if(len==3) return Math.max(Math.max(nums[0],nums[1]),nums[2]);
        if(len==4) return Math.max(nums[0]+nums[2],nums[1]+nums[3]);
        int[] dp=new int[len-1];
        dp[0]=nums[0];
        dp[1]=nums[1];
        dp[2]=nums[0]+nums[2];
        for(int i=3;i<len-1;++i){
            dp[i]=nums[i]+Math.max(dp[i-2],dp[i-3]);
        }
        int max=Math.max(dp[len-3],dp[len-2]);
        dp[0]=nums[1];
        dp[1]=nums[2];
        dp[2]=nums[1]+nums[3];
        for(int i=3;i<len-1;++i){
            dp[i]=nums[i+1]+Math.max(dp[i-2],dp[i-3]);
        }
        max=Math.max(max,dp[len-2]);
        max=Math.max(max,dp[len-3]);
        return max;
    }
}
